<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 数字游戏（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>小明玩一个游戏。</p> 
<p>系统发1&#43;n张牌&#xff0c;每张牌上有一个整数。</p> 
<p>第一张给小明&#xff0c;后n张按照发牌顺序排成连续的一行。</p> 
<p>需要小明判断&#xff0c;后n张牌中&#xff0c;是否存在连续的若干张牌&#xff0c;其和可以整除小明手中牌上的数字。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入数据有多组&#xff0c;每组输入数据有两行&#xff0c;输入到文件结尾结束。</p> 
<p>第一行有两个整数n和m&#xff0c;空格隔开。m代表发给小明牌上的数字。</p> 
<p>第二行有n个数&#xff0c;代表后续发的n张牌上的数字&#xff0c;以空格隔开。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>对每组输入&#xff0c;如果存在满足条件的连续若干张牌&#xff0c;则输出1;否则&#xff0c;输出0</p> 
<p></p> 
<h4>备注</h4> 
<ul><li>1 ≤ n ≤ 1000</li><li>1 ≤ 牌上的整数 ≤ 400000</li><li>输入的组数&#xff0c;不多于1000</li><li>用例确保输入都正确&#xff0c;不需要考虑非法情况。</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">6 7<br /> 2 12 6 3 5 5<br /> 10 11<br /> 1 1 1 1 1 1 1 1 1 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;"> <p>1</p> <p>0</p> </td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">两组输入。第一组小明牌的数字为7&#xff0c;再发了6张牌。第1、2两张牌教字和为14&#xff0c;可以整除7&#xff0c;输出1&#xff0c;第二组小明牌的教字为11&#xff0c;再发了10张牌&#xff0c;这10张牌数字和为10&#xff0c;无法整除11&#xff0c;输出0。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题考察前缀和知识&#xff0c;以及数学问题。</p> 
<p></p> 
<p>本题要求连续若干张牌的和&#xff0c;其实就是求区间的元素之和。</p> 
<p>而求解任意区间和的最佳算法就是&#xff1a;前缀和之差&#xff0c;这个知识点可以看下</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/128976936" rel="nofollow" title="算法设计 - 前缀和 &amp; 差分数列_伏城之外的博客-CSDN博客">算法设计 - 前缀和 &amp; 差分数列_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<p>利用前缀和&#xff0c;我们可以在O(1)的时间求解出[L,R]区间和 &#61; preSum[R] - preSum[L-1]。</p> 
<p>那么接下来&#xff0c;我们是否需要双重for遍历出所有区间&#xff0c;然后逐一验证对应区间和是否可以整除k呢&#xff1f;</p> 
<p>本题中每组用例最多n &#61; 1000张牌&#xff0c;因此双重for遍历对应牌的所有连续区间的时间复杂度O(n^2)。</p> 
<p>而本题有最多有1000组用例&#xff0c;因此相当于O(n^3)的时间复杂度&#xff0c;这是非常容易超时的。</p> 
<p></p> 
<p>本题优化是基于一个数学性质&#xff1a;</p> 
<blockquote> 
 <p>如果两个数a,b&#xff0c;他们的差a - b可以被k整除&#xff0c;则必然 a % k &#61;&#61; b % k。</p> 
 <p>反之&#xff0c;如果a % k &#61;&#61; b % k&#xff0c;那么 a - b 必然可以被k整除。</p> 
</blockquote> 
<p>大家可以自行验证下这个数学性质。</p> 
<p>验证好后&#xff0c;我们只需要将preSum[R]带入a&#xff0c;preSum[L-1]带入b 再来看看&#xff1a;</p> 
<p>如果preSum[R] % k &#61;&#61; preSum[L-1] % k&#xff0c;那么必然 preSum[R] - preSum[L-1] 可以被k整除。</p> 
<p></p> 
<p>利用这个数学性质&#xff0c;我们就不必双重for遍历所有区间了&#xff0c;只需要检查preSum数组中是否存在两个元素 % k 的结果相同&#xff0c;即可说明存在区间之和可以整除k。</p> 
<p></p> 
<hr /> 
<p>2023.08.19 根据考友反馈&#xff0c;本题python代码输入获取逻辑存在问题&#xff0c;</p> 
<p>本题的输入是没有截止条件的&#xff0c;因此我这边默认将输入空行作为截止条件。</p> 
<p>但是考到这题的考友反馈&#xff0c;这题按这种逻辑处理输入是不行的&#xff0c;需要死循环获取输入&#xff0c;每获取到一组输入&#xff0c;就要立即输出对应解。</p> 
<p>核心代码逻辑没问题&#xff0c;可以100%。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  while (true) {
    try {
      const [n, m] &#61; (await readline()).split(&#34; &#34;).map(Number);
      const nums &#61; (await readline()).split(&#34; &#34;).map(Number);
      console.log(isExsit(nums, m));
    } catch (error) {
      break;
    }
  }
})();

function isExsit(nums, m) {
  const remain &#61; new Set();
  remain.add(0);

  let sum &#61; 0;
  for (let num of nums) {
    sum &#43;&#61; num;
    if (remain.has(sum % m)) {
      return 1;
    } else {
      remain.add(sum % m);
    }
  }

  return 0;
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    while (sc.hasNextLine()) {
      try {
        int[] tmp &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
        int[] nums &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
        System.out.println(isExist(nums, tmp[1]));
      } catch (Exception e) {
        break;
      }
    }
  }

  public static int isExist(int[] nums, int m) {
    HashSet&lt;Integer&gt; remain &#61; new HashSet&lt;&gt;();
    remain.add(0);

    int sum &#61; 0;
    for (int num : nums) {
      sum &#43;&#61; num;
      if (remain.contains(sum % m)) {
        return 1;
      } else {
        remain.add(sum % m);
      }
    }

    return 0;
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">def isExist(nums, m):
    remain &#61; set()
    remain.add(0)

    total &#61; 0
    for num in nums:
        total &#43;&#61; num
        if total % m in remain:
            return 1
        else:
            remain.add(total % m)

    return 0


# 输入获取
while True:
    try:
        n, m &#61; map(int, input().split())
        nums &#61; list(map(int, input().split()))
        print(isExist(nums, m))
    except ValueError:
        break
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>